This specification relates to path computation in spatial networks.
The problem of point-to-point fastest path computation in spatial networks is extensively studied with many approaches proposed to speed-up the computation. Most of the existing approaches make the simplifying assumption that travel-times of the network edges are constant. With the ever-growing popularity of online map applications and their wide deployment in mobile devices and car-navigation systems, an increasing number of users search for point-to-point fastest paths and the corresponding travel-times. On static road networks where edge costs are constant, this problem has been extensively studied and many efficient speed-up techniques have been developed to compute the fastest path in a matter of milliseconds (e.g., Hanan Samet and Jagan Sankaranarayanan and Houman Alborzi, Scalable Network Distance Browsing in Spatial Databases, SIGMOD, pages 33-40, Toronto, Canada, 2008; Ulrith Lauther, An Extremely Fast, Exact Algorithm for Finding Shortest Paths in Static Networks with Geographical Background, Geoinformation and Mobilitat, pages 33-40, Toronto, Canada, 2004; Wagner, Dorothea and Willhalm, Thomas, Geometric Speed-Up Techniques for Finding Shortest Paths in Large Sparse Graphs, ESA, 2003; P. Sanders and D. Schultes, Highway hierarchies hasten exact shortest path queries, ESA, 2005; and Sanders, Peter and Schultes, Dominik, Engineering fast route planning algorithms, WEA, 2007).